package top.humbleyuan.test.demo;

import java.util.Arrays;

/**
 * @Author HumbleYuan
 * @Date 2020/4/22 17:39
 * @Des
 */
public class T4 {

    // 快排
    public static void main(String[] args) {
        int[] nums = {3,6,1,89,56,45,22};

        quickSort(nums, 0, nums.length - 1);

        System.out.println(Arrays.toString(nums));
    }

    public static void quickSort(int[] nums, int begin, int end) {
        if(begin > end) {
            return;
        }


        int i = begin, j = end;
        int base = nums[begin];

        while(i < j) {

            // 这里两个顺序为什么不能变,高位和低位
            while(nums[j] >= base && i < j) {
                j--;
            }

            System.out.println();

            while(nums[i] <= base && i < j) {
                i++;
            }

            if(i < j) {
                swap(nums, i, j);
            }

        }

        swap(nums, begin, i);
        quickSort(nums, begin, j - 1);
        quickSort(nums, j + 1, end);
    }

    public static void swap(int[] nums, int m, int n) {
        int temp = nums[m];
        nums[m] = nums[n];
        nums[n] = temp;
    }
}
